The structured query language (SQL) is a non-procedural program language. Although it supports the query of databases via database management systems, it does not specifically delineate how to search for data. The SQL language implies the existence of a query optimizer to find the desired data in a database query task. Generally, query optimizers are machines that input a query and produce a good plan choice for execution of a search of the database. Optimizers may make choices based on statistics on the information within the database, query predicate selectivity, and cardinality estimates (intermediate result sizes). Query plans are then generated and subsequently executed.
The cost of performing a query may be measured in I/O accesses. The greater the number of I/O accesses, the less efficient the performance of a query. Moreover, random I/O accesses are less efficient than sequential I/O accesses. An efficient query plan will obtain the desired data with as few I/O accesses as possible and, whenever possible, will minimize the use of random I/O accesses in favor of sequential I/O accesses. Inefficient query performance may be the result of a bad choice made by the optimizer in constructing a query plan. A poor performance choice in a query plan may be made based on inaccurate cardinality estimates. Cardinality estimates are derived from statistics concerning the information in the database and are affected both by inaccurate statistics and by excessively complex predicates. That is, even with perfectly accurate statistics, some predicates are too complex to allow for accurate estimates.
It has been observed that one possible improvement to the specific problem of querying a database is to consider performing a sort for greater fetch efficiency. In fact, sorts are known to be of help in the cases of fetch, index nested loop join, insert, update, and delete. Presently, once a query plan has been chosen based on the best available statistics concerning the database, there is little opportunity to change the progress of a plan while it is being executed. There is currently no method of recovering from a poor performance plan without stopping the execution of the original plan, discarding any existing results, reformulating the plan, executing the reformulated plan and retrieving new results in a manner that utilizes past results.
Thus, there is a need for a technique to adaptively change a query plan during execution without losing row data already retrieved. The present invention addresses the aforementioned needs and solves them with additional advantages as expressed herein.